class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

// 递归
function isSymmetric(root: TreeNode | null): boolean {
    if (root === null) return true;
    return isMirror(root.left, root.right);
}

// 辅助函数：判断两棵树是否镜像对称
function isMirror(t1: TreeNode | null, t2: TreeNode | null): boolean {
    // 两个节点都为空，对称
    if (t1 === null && t2 === null) return true;

    // 一个为空一个不为空，不对称
    if (t1 === null || t2 === null) return false;

    // 节点值不相等，不对称
    if (t1.val !== t2.val) return false;

    // 递归检查：t1的左子树和t2的右子树对称，且t1的右子树和t2的左子树对称
    return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}

// 迭代 -- 队列
function isSymmetric1(root: TreeNode | null): boolean {
    if (root === null) return true;
    const queue: (TreeNode | null)[] = [root.left, root.right];
    while (queue.length > 0) {
        const t1 = queue.shift();
        const t2 = queue.shift();
        if (t1 === null && t2 === null) continue;
        if (t1 === null || t2 === null) return false;
        if (t1!.val !== t2!.val) return false;
        queue.push(t1!.left, t2!.right, t1!.right, t2!.left);
    }
    return true;
}